package com.zang.dp;

/**
 * @author Cizai
 * @since 2022/11/28 21:17
 * @see <a href="https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/">...</a>
 **/
public class 买卖股票的最佳时机IV {

    public int maxProfit(int k, int[] prices) {

        int[][] dp = new int[prices.length][k*2+1];

        // 初始化第一天的时候第n次购买的情况
        for (int i = 1; i < k*2; i+=2){
            dp[0][i] = -prices[i];
        }


        for (int i = 1;i < prices.length; i ++) {
            // 对第i天的第j次购买股票
            for (int j = 1; j< dp[i].length; j+=2){
                // 第一次持有股票的情况下 可能为上一次就持有，或者这一次买了
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j-1] - prices[i]);
                // 第二次没持有股票的情况就是，上一次也没有持有，或者把上次持有的卖掉了
                dp[i][j+1] = Math.max(dp[i - 1][j+1], dp[i - 1][j] + prices[i]);
            }
        }
        return dp[prices.length - 1][k*2];
    }
}
